// 来自 noipnoi清北更精妙
#include <bits/stdc++.h>
using namespace std;

const int N = 10, S = (1 << 7) + 5, INF = 1e9;
int n, m;
int dp[N][S + 5];
int c[N];
int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
      string str;
      cin >> str;
      c[i] = 0;
      for (int j = 1; j <= m; ++j)
        if (str[j - 1] == '#')
          c[i] |= (1 << j - 1);
    }

    // dp[i][s]:  考虑前i行，第i行的状态为s:0,1,2,3.. 2^m-1的最小代价
    for (int i = 0; i <= n; ++i)
      for (int s = 0; s < (1 << m); ++s)
        dp[i][s] = INF;

    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
      for (int s1 = 0; s1 < (1 << m); ++s1)     // 枚举第i-1行 的状态s1
        for (int s2 = 0; s2 < (1 << m); ++s2) { // 枚举第i行 的状态s2

          // 判断2*2是否全黑
          int s = s1 & s2; // s1和s2的公共位

          // 检查s的二进制表示中是否存在相邻的1。
          // 如果存在相邻的1，则s & (s >> 1)的结果将不为0，触发continue语句。
          if (s & (s >> 1))
            continue;

          dp[i][s2] =
              min(dp[i][s2], dp[i - 1][s1] + __builtin_popcount(s2 ^ c[i]));
          // s2^c[i]表示s2和c[i]的不同位的数量
        }
    }
    int ans = INF;
    for (int s = 0; s < (1 << m); ++s)
      ans = min(ans, dp[n][s]); 
    
    cout << ans << endl;
  }
  return 0;
}
